First we pointed out that there is a powerful optimization scheme in nature, known on the computer as simulated annealing, which has not been applied in computer go. We proceeded to adapt simulated annealing to the problem of finding the best move in the game tree of go. The adaptation is based on the observation that there is a certain move reorder invariance in go. There are two key elements to our proposal: 1) We suggest that the timeliness of a move is a good objective function for simulated annealing; 2) Playing games to the very end can substitute for go heuristics. Finally, we presented first test results of a computer implementation of our algorithm that plays go clearly above the absolute beginner's level of 30 kyu.
Since the idea seems to work in practice, we would like to point out several interesting avenues for further exploration. First let us comment about the relevance of the algorithm for two features of computer go, tree searches and evaluation functions. A lot of research has been done on α-β pruning and related algorithms. One should perform a quantitative study of how simulated annealing performs for the different orders of implementation (one move, two move, ... sequences), and find out how well the method can do in practice (see Chs. 1–3 of [11]). Recall that for the traveling salesman problem the computational effort was reduced tremendously. Here we face the additional problem that our objective function for tree searches is an approximation.
As far as evaluation functions are concerned, an age old dream of game related artificial intelligence is to tell the machine the rules, and nothing else, and have it play a perfect game. Although Gobble plays very poorly by human standards, whatever ``understanding'' of go Gobble has was not fed in by humans in the form of go heuristics. The fact that points are best counted when the game is over apparently is important enough to matter even through the haze of random games and poor statistics. It is open whether this phenomenon can be utilized, for example, on larger boards.
So far we have studied simulated annealing in its pure form only to identify its characteristica. We definitely do not want to suggest that this is the best way to program go. Strong go programs like Many Faces of Go succeed because they apply a collection of ideas like pattern matching, tactical analysis and influence potentials. The most difficult problem is to combine all methods into one well-rounded computer go player. Just because Gobble shows some aptitude in tree searches and evaluation does not mean that this is the optimal strategy under all circumstances. Whenever exact methods are available, say local or small scale tactical searches (e.g. for ladders), they are much superior to statistical methods.
For example, we noticed that Gobble is particularly weak when it comes to defending its territory near borders. The correct moves are elementary patterns most good programs know. Indeed, one promising way to improve Gobble could be the addition of a pattern library. This could be implemented on the top level of the move tree for alternatives which are hard to distinguish. The same applies to all standard techniques. A pattern library might have an advantage over other methods if pattern matching is sufficiently fast to allow its inclusion at all stages of the random games. The stronger the computer player is that plays the random games, the more representative the final results are.
On the technical side, let us mention that simulated annealing is well-suited for special computer hardware. Computers are good at simple repetitive tasks, which is in contrast to the requirements of many applications in artificial intelligence where the main problem is programming and manipulating complicated structures, e.g. in expert systems for go. Monte Carlo simulations are a prime example for number crunching. Simulated annealing is easily implemented on parallel computers [11], which are the most powerful and affordable computing resource today. Another approach to increase the raw computing speed in Gobble combined with a pattern library is dedicated hardware. In fact, there is an ongoing project to design a fast VLSI chip which incorporates precisely the two functions which are most time consuming in such an algorithm, move generation and pattern matching [12].
To summarize, simulated annealing seems to be a promising idea about how to approach computer go from a new direction. Simulated annealing is certainly not a magic wand which resolves all the profound problems related to computer go. But we believe it is quite possible that simulated annealing could become an integral part of the go programmer's repertoire.